package com.hyb.algorithm.data.struct.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 40. 组合总和 II
 * https://leetcode.cn/problems/combination-sum-ii/description/
 * @author: ybhu
 * @create: 2023/12/29 17:24
 *
 */
public class CombinationSumII {


    private List<List<Integer>> res;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new ArrayList<List<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();

        Arrays.sort(candidates);
        backTrack(candidates, target, 0, list);

        return res;
    }


    public void backTrack(int[] candidates, int target, int start, List<Integer> list) {


        if (target < 0) {
            return;
        }

        if (target == 0) {
            res.add(new ArrayList(list));
            return;
        }

        for (int index = start; index < candidates.length; index++) {
            if (target - candidates[index] < 0) {
                continue;
            }

            //重复元素过来
            if (index > start && candidates[index] == candidates[index - 1]) {
                continue;
            }

            list.add(candidates[index]);
            backTrack(candidates, target - candidates[index], index + 1, list);
            //回溯重置
            list.remove(list.size() - 1);

        }


    }

}
